package cn.springcloud.fix.demo.leecode;

import java.util.*;

public class Test00 {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 55, 5, 3, 7, 2, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + "\t");
        }

        int[] arr2 = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int res = maxSubArray(arr2);
        System.out.println(res);

        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        res = maxProfit2(prices);

        System.out.println(111);
    }

    // 柱状图中最大的矩形, https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;

        int res = 0;
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            int curHeight = heights[i];
            // 找左边最后 1 个大于等于 heights[i] 的下标
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }
            // 找右边最后 1 个大于等于 heights[i] 的索引
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }
            int width = right - left + 1;
            res = Math.max(res, width * curHeight);
        }
        return res;
    }

    // 最大矩形, https://leetcode-cn.com/problems/maximal-rectangle/
    public static int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (char[] chars : matrix) {
            //遍历每一列，更新高度
            for (int col = 0; col < matrix[0].length; col++) {
                if (chars[col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    //买卖股票的最佳时机，暴力法
    public static int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                max = Math.max(max, prices[j] - prices[i]);
            }
        }
        return max;
    }

    //买卖股票的最佳时机，一次遍历
    public static int maxProfit2(int[] prices) {
        int max = 0;
        int minprice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > max) {
                max = prices[i] - minprice;
            }
        }
        return max;
    }

    //给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    public static int maxSubArray(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            max = Math.max(max, pre);
        }
        return max;
    }

    //三数之和，https://leetcode-cn.com/problems/3sum/
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;//三数和为0，则必定第一个是负数
            if (i > 0 && nums[i - 1] == nums[i]) {//不能有重复数
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    result.add(list);
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++;
                    }
                    while (j < k && nums[k - 1] == nums[k]) {
                        k--;
                    }
                    //往中间靠拢
                    j++;
                    k--;
                } else if (nums[i] + nums[j] + nums[k] < 0) {//说明j要右移
                    j++;
                } else {//说明k要左移
                    k--;
                }
            }
        }
        return result;
    }

    //快速排序
    private static void quickSort(int[] arr, int low, int high) {
        if (low >= high) return;
        int left = low;
        int right = high;
        int key = arr[left];

        while (left < right) {
            //先从右往左找到比基准小的，覆盖到基准的位置
            while (left < right && arr[right] >= key) {
                right--;
            }
            arr[left] = arr[right];
            //再从左往右找到比基准大的，覆盖到刚才的 right 位置
            while (left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];
        }

        //基准归位
        arr[left] = key;

        quickSort(arr, low, left - 1);
        quickSort(arr, right + 1, high);
    }

    //反转链表 Test06
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head.getNext() != null) {
            head.setNext(pre);
            pre = head;
            head = head.getNext();
        }
        return head;
    }

    //判断是否是环链
    private static boolean hasCycle(ListNode head) {
        return false;
    }

    /**
     * (())()
     * int r = scoreOfParentheses("(()(()))"); Test01
     */
    private static int scoreOfParentheses2(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(0);
            } else {
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 + Math.max(1, 2 * v1));
            }
        }
        return stack.pop();
    }

    // Test05
    private static void reverseString(String abc) {

    }

    // 树的高度 Test07
    private static int heightOfTree(Node node) {
        if (node == null) return 0;
        int left = heightOfTree(node.getLeft());
        int right = heightOfTree(node.getRight());
        return Math.max(left, right) + 1;
    }

    //层序遍历
    private static List<List<Object>> levelOrder(Node node) {
        return null;
    }

    //前序遍历
    private static void preOrder(Node node) {

    }

    //打印二叉树所有路径
    private static List<String> binaryTreePaths2(Node node) {
        return null;
    }

    // 一个字符串里最长不重复子串的长度
    public static int lengthOfLongestSubstring3(String s) {
        return 0;
    }

    // 将两个升序链表合并为一个新的 升序 链表并返回
    public static ListNode mergeTwoLists(ListNode l, ListNode r) {
        return null;
    }
}
